package assign1;
/* COMP 3760 - Algorithm Analysis and Design
 * Assignment #1 - Mnemonic Monkey
 * Stacy Mitchell	A00816991
 * Vukasin Simic	A00801474
 * 
 * October 14, 2012
 * 
 * Permutation.java
 * 
 * 
 * Abstract class containing the lexicographicPermute() function that generates a List of all permutations for the given input set.
 * 
 */
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;

abstract public class Permutation {
	
	/* Java equivalent of LexicographicPermute(n) Pseudocode p 146: Design and Analysis of Algorithms - Levitin
	   This version is not used by Mnemonic, instead the following lexicographicPermute method with a changed signature is used.*/
	public static List<List<Integer>> lexicographicPermute(int n){
		List<List<Integer>> permutations = new ArrayList<List<Integer>>();
		List<Integer> single_permutation = getFirstPermutation(n);
		permutations.add(single_permutation); //single_permutation.toArray(new Integer[n])
		
		int i;
		int j;
		while((i = hasTwoConsecutiveIncreasing(single_permutation)) != -1){
			j = farthestLargerIndex(single_permutation, i);
			Collections.swap(single_permutation,i,j);
			Collections.reverse(single_permutation.subList(i + 1, n));
			permutations.add(single_permutation);
		}
		return permutations;
	}
	
	/*Based on LexicographicPermute(n) p 146: Design and Analysis of Algorithms - Levitin
	  Instead of taking an Integer n, as a parameter and generating n! permutations in lexicographic order
	  with the first permutation being: {1,2,3, ..., n-1, n}, an ordered list of lab numbers is accepted
	  as the parameter (e.g. {2,5,6,7,10,11}) which is used as the first permutation from which to generate
	  the rest of the n! (where n is the size of the input list) permutations in lexicographic order. Also
	  instead of returing the generated permuations, it checks all of them and returns only the fastest one.*/
	public static List<Integer> lexicographicPermute(List<Integer> set, List<Map<String, Integer>> lab_list, long programStartTime, long caseStartTime) {
		int n = set.size();
		List<Integer> single_permutation = set;
		List<Integer> temp;
		
		List<Integer> best_set_permutation = set; // The fastest arrangement of a Subset
		double best_set_time = Mnemonic.getPathTimeInHours(lab_list, set); // The time of the Subset's fastest arrangement
		double permutation_time; // a Subset permutation's time
		
		int i;
		int j;
		while((i = hasTwoConsecutiveIncreasing(single_permutation)) != -1){
			temp = new ArrayList<Integer>();
			temp.addAll(single_permutation);
			single_permutation = temp;
			
			j = farthestLargerIndex(single_permutation, i);
			Collections.swap(single_permutation,i,j);
			Collections.reverse(single_permutation.subList(i + 1, n));
			
			//check single_permutation's time, compare its speed to that of the best permutation seen so far
			permutation_time = Mnemonic.getPathTimeInHours(lab_list, single_permutation);
			if (permutation_time < best_set_time){
				best_set_time = permutation_time;
				best_set_permutation = single_permutation;
			}
			Mnemonic.checkTimeout(programStartTime, caseStartTime);
		}
		return best_set_permutation;
	}
	
	//Used by lexicographicPermute(int n) to generate the first permutation to {1,2,3...,n}
	private static List<Integer> getFirstPermutation(int n){
		List<Integer> first_permutation = new ArrayList<Integer>();
		for (int i = 1; i <= n; i++){
			first_permutation.add(i);
		}
		return first_permutation;
	}
	
	//Used by the lexicographicPermute algorithm to check if the given permutation has any consecutive increasing elements.
	private static int hasTwoConsecutiveIncreasing(List<Integer> list){
		
		for(int i =  list.size() - 2; i >= 0; i--){
			if (list.get(i) < list.get(i + 1)){
				return i;
			}  
		}
		return -1;
	}
	
	//Used by the lexicographicPermute algorithm to get the given permutation farthest index containing a value larger than the given index.
	private static int farthestLargerIndex(List<Integer> list, int index){
		int compareTo = list.get(index);
		for(int i =  list.size() - 1; i > 0; i--){
			if (list.get(i) > compareTo){
				return i;
			}  
		}
		return index;
	}
}
